4.17 The Euclidean algorithm has been known for over 2000 years and has always been a favorite among number theorists. After these many years, there is now a potential competitor, invented by J. Stein in 1961. Stein"s algorithms is as follows. Determine gcd(A, B) with A, B >= 1. STEP 1 Set A1 = A, B1 = B, C1 = 1 STEP n 1. If An = Bn stop. gcd(A, B) = AnCn 2. If An and Bn are both even, setA n+1 = An/2, Bn+1 = Bn/2, Cn+1 = 2Cn 3. If An is even and Bn is odd, set An+1 = An/2, Bn+1 = Bn, Cn+1 = Cn 4. If An is odd and Bn is even, set An+1 = An, Bn+1 = Bn/2, Cn+1 = Cn 5. If An and Bn are both odd, setA n+1 = |An Bn|, Bn + 1 = min(Bn, An), Cn+1 = Cn Continue to step n + 1. To get a feel for the two algorithms, compute gcd(2152, 764) using both the Euclidean and Stein"s algorithm. a. To get a feel for the two algorithms, compute gcd(2152, 764) using both the Euclidean and Stein"s algorithm. b. What is the apparent advantage of Stein"s algorithm over the Euclidean algorithm? | |
| View Solution | |
| << Back | Next >> |